#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

//vector<int> nextGreaterElements(vector<int>& nums) {
//    priority_queue<PII, vector<PII>, greater<PII>> pq;
//    vector<int> res(nums.size(), -1);
//    int n = nums.size();
//    vector<int> num(n * 2);
//    for (int i = 0; i < n; i++)    num[i] = num[i + n] = nums[i];
//
//    for (int i = 0; i < n * 2; i++)
//    {
//        if (pq.size())
//        {
//            while (pq.size())
//            {
//                auto t = pq.top();
//                if (t.first >= num[i])    break;
//                if (res[t.second] == -1)
//                    res[t.second] = num[i];
//                pq.pop();
//            }
//        }
//        pq.push({ num[i],i % n });
//    }
//    return res;
//}
//
//int main()
//{
//    vector<int> nums = { 5,4,3,2,1 };
//    vector<int> res = nextGreaterElements(nums);
//    for (auto it : res)  cout << it << " ";
//    return 0;
//}

//vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//    int n = nums.size();
//    deque<PII> stk;
//    vector<int> ans;
//    int nmax = INT_MIN;
//
//    for (int i = 0; i < n; i++)
//    {
//        while (stk.size() && stk.front().second + k - 1 < i) stk.pop_front();
//        while (stk.size() && stk.back().first < nums[i]) stk.pop_back();
//        stk.push_back({ nums[i],i });
//        if (i >= k - 1)  ans.push_back(stk.front().first);
//    }
//    return ans;
//}

//typedef pair<int, int> PII;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };


int orangesRotting(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    auto bfs = [&]() -> int {
        vector<vector<bool>> st(grid.size(), vector<bool>(grid[0].size()));
        queue<PII> q;
        int num = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1) num++;
                else if (grid[i][j] == 2)
                {
                    q.push({ i,j });
                    st[i][j] = true;
                }

        int count = 0;
        int step = 0;
        while (q.size())
        {
            int len = q.size();
            for (int j = 0; j < len; j++)
            {
                auto t = q.front();
                q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int a = dx[i] + t.first, b = dy[i] + t.second;
                    if (a < 0 || a >= n || b < 0 || b >= m)   continue;
                    if (st[a][b])    continue;
                    if (grid[a][b] != 1) continue;
                    count++;
                    if (count == num)    return step + 1;

                    st[a][b] = true;
                    q.push({ a,b });
                }
            }
            step++;
        }
        if (num == count)    return step;
        return -1;
    };
    return bfs();
}

int main()
{
    vector<vector<int>> nums = { {2,1,1 }, { 1,1,0 }, { 0,1,1 }};
    cout << orangesRotting(nums);
    return 0;
}